{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Valid Word Abbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validWordAbbreviation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效单词缩写"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串可以用 <strong>缩写</strong> 进行表示，<strong>缩写</strong> 的方法是将任意数量的 <strong>不相邻</strong> 的子字符串替换为相应子串的长度。例如，字符串 <code>\"substitution\"</code> 可以缩写为（不止这几种方法）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"s10n\"</code> (<code>\"s <em><strong>ubstitutio</strong></em> n\"</code>)</li>\n",
    "\t<li><code>\"sub4u4\"</code> (<code>\"sub <em><strong>stit</strong></em> u <em><strong>tion</strong></em>\"</code>)</li>\n",
    "\t<li><code>\"12\"</code> (<code>\"<em><strong>substitution</strong></em>\"</code>)</li>\n",
    "\t<li><code>\"su3i1u2on\"</code> (<code>\"su <em><strong>bst</strong></em> i <em><strong>t</strong></em> u <em><strong>ti</strong></em> on\"</code>)</li>\n",
    "\t<li><code>\"substitution\"</code> (没有替换子字符串)</li>\n",
    "</ul>\n",
    "\n",
    "<p>下列是不合法的缩写：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"s55n\"</code>&nbsp;(<code>\"s&nbsp;<u>ubsti</u>&nbsp;<u>tutio</u>&nbsp;n\"</code>，两处缩写相邻)</li>\n",
    "\t<li><code>\"s010n\"</code>&nbsp;(缩写存在前导零)</li>\n",
    "\t<li><code>\"s0ubstitution\"</code>&nbsp;(缩写是一个空字符串)</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串单词 <code>word</code> 和一个缩写&nbsp;<code>abbr</code>&nbsp;，判断这个缩写是否可以是给定单词的缩写。</p>\n",
    "\n",
    "<p><strong>子字符串</strong>是字符串中连续的<strong>非空</strong>字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"internationalization\", abbr = \"i12iz4n\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>单词 \"internationalization\" 可以缩写为 \"i12iz4n\" (\"i <em><strong>nternational</strong></em> iz <em><strong>atio</strong></em> n\") 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>word = \"apple\", abbr = \"a2e\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>单词 \"apple\" 无法缩写为 \"a2e\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word.length &lt;= 20</code></li>\n",
    "\t<li><code>word</code> 仅由小写英文字母组成</li>\n",
    "\t<li><code>1 &lt;= abbr.length &lt;= 10</code></li>\n",
    "\t<li><code>abbr</code> 由小写英文字母和数字组成</li>\n",
    "\t<li><code>abbr</code> 中的所有数字均符合 32-bit 整数范围</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [valid-word-abbreviation](https://leetcode.cn/problems/valid-word-abbreviation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [valid-word-abbreviation](https://leetcode.cn/problems/valid-word-abbreviation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"internationalization\"\\n\"i12iz4n\"', '\"apple\"\\n\"a2e\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        wStart, aStart = 0, 0\n",
    "        aLen = len(abbr)\n",
    "        wLen = len(word)\n",
    "\n",
    "        while aStart < aLen:\n",
    "            if abbr[aStart] == '0':\n",
    "                return False\n",
    "\n",
    "            if str.isdigit(abbr[aStart]):\n",
    "                count = abbr[aStart]\n",
    "                aStart += 1\n",
    "                while aStart < aLen:\n",
    "                    if str.isdigit(abbr[aStart]):\n",
    "                        count += abbr[aStart]\n",
    "                        aStart += 1\n",
    "                    else:\n",
    "                        break\n",
    "                wStart += int(count)\n",
    "            else:\n",
    "                if wStart > wLen -1 or word[wStart] != abbr[aStart]:\n",
    "                    return False\n",
    "\n",
    "                aStart += 1\n",
    "                wStart += 1\n",
    "\n",
    "\n",
    "        return wStart == wLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        j = 0\n",
    "        num = 0\n",
    "        for i in range(len(abbr)):\n",
    "            if '0'<=abbr[i]<='9':\n",
    "                if num==0 and abbr[i]=='0':return False\n",
    "                num = num*10+int(abbr[i])\n",
    "            else:\n",
    "                j+=num\n",
    "                num = 0\n",
    "                if j>=len(word) or word[j]!=abbr[i]: return False\n",
    "                j+=1\n",
    "        j+=num\n",
    "        return True if j==len(word) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        wordIdx = 0\n",
    "        abbrIdx = 0\n",
    "\n",
    "        while abbrIdx < len(abbr):\n",
    "            left = abbrIdx\n",
    "            while abbrIdx < len(abbr) and '0' <= abbr[abbrIdx] <= '9':\n",
    "                abbrIdx += 1\n",
    "\n",
    "            if left == abbrIdx: # cur is char\n",
    "                if wordIdx >= len(word) or word[wordIdx] != abbr[abbrIdx]:\n",
    "                    return False\n",
    "                wordIdx += 1\n",
    "                abbrIdx += 1\n",
    "            else: # num\n",
    "                if abbr[left] == '0': # leading 0\n",
    "                    return False\n",
    "                wordIdx += int(abbr[left: abbrIdx])\n",
    "                if wordIdx > len(word):\n",
    "                    return False\n",
    "                \n",
    "        return (abbrIdx == len(abbr) and wordIdx == len(word))\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "'''\n",
    "abbreviation\n",
    "           ^\n",
    "a10n\n",
    "   ^\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        p1, p2 = 0, 0\n",
    "        m, n = len(word), len(abbr)\n",
    "        while p1 < m and p2 < n:\n",
    "            if abbr[p2].isalpha():\n",
    "                if word[p1] == abbr[p2]:\n",
    "                    p1 += 1\n",
    "                    p2 += 1\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if abbr[p2] == \"0\":\n",
    "                    return False\n",
    "                # digit\n",
    "                p3 = p2\n",
    "                while p3 < n and abbr[p3].isdigit():\n",
    "                    p3 += 1\n",
    "\n",
    "                num = int(abbr[p2:p3])\n",
    "                p1 += num\n",
    "                p2 = p3\n",
    "\n",
    "        if p1 == m and p2 == n:\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        \"\"\" two pointers \"\"\"\n",
    "\n",
    "        n1, n2 = len(word), len(abbr)\n",
    "        if n1 < n2:\n",
    "            return False \n",
    "\n",
    "        p1, p2 = 0, 0 \n",
    "        while p1 < n1 and p2 < n2:\n",
    "            if abbr[p2] == '0':  # pre-zero\n",
    "                return False \n",
    "            elif abbr[p2].isdigit():\n",
    "                temp = 0 \n",
    "                # get the abbr number cnt \n",
    "                while p2 < n2 and abbr[p2].isdigit():\n",
    "                    temp = temp * 10 + int(abbr[p2])\n",
    "                    p2 += 1 \n",
    "                p1 += temp \n",
    "            else:\n",
    "                if word[p1] != abbr[p2]:\n",
    "                    return False \n",
    "                p1 += 1 \n",
    "                p2 += 1 \n",
    "\n",
    "        return p1 == n1 and p2 == n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(word) and j < len(abbr):\n",
    "            if word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                continue\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] =='0': return False\n",
    "                cnt = 0\n",
    "                k = j \n",
    "                while k < len(abbr) and abbr[k].isdigit(): # move forward with while, first condition is the valid conditoin and the second condition is the actual condition\n",
    "                    cnt = cnt * 10 + int(abbr[k])\n",
    "                    k += 1\n",
    "                i += cnt \n",
    "                j = k\n",
    "            else:\n",
    "                break \n",
    "        return i == len(word) and j == len(abbr)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n1, n2 = len(word), len(abbr)\n",
    "\n",
    "        while left<n1 and right<n2:\n",
    "            if \"a\"<=abbr[right]<=\"z\":\n",
    "                if word[left]!=abbr[right]:\n",
    "                    return False \n",
    "                else:\n",
    "                    left += 1\n",
    "                    right += 1\n",
    "            \n",
    "            else:\n",
    "                if abbr[right]==\"0\":\n",
    "                    return False \n",
    "                else:\n",
    "\n",
    "                    \n",
    "                    val = 0\n",
    "                    while right<n2 and \"0\"<=abbr[right]<=\"9\":\n",
    "                        val = 10*val+int(abbr[right])\n",
    "                        right += 1\n",
    "                    left += val \n",
    "                    if left>n1:\n",
    "                        return False\n",
    "        return (left==n1 and right==n2)\n",
    "                    \n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Boring implementation detail question, review and recite.\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        word_len, abbr_len = len(word), len(abbr)\n",
    "        cur_word_idx, cur_abbr_idx = 0, 0\n",
    "        while cur_abbr_idx < abbr_len:\n",
    "            if cur_word_idx >= word_len: return False\n",
    "            cur_count = 0\n",
    "            while cur_abbr_idx < abbr_len and abbr[cur_abbr_idx].isdigit(): # 1RE: index out of range\n",
    "                if cur_count == 0 and abbr[cur_abbr_idx] == '0': return False # 2WA: leading zero return false, need confirm with interviewer\n",
    "                cur_count = cur_count * 10 + int(abbr[cur_abbr_idx])\n",
    "                cur_abbr_idx += 1\n",
    "            if cur_count != 0:\n",
    "                if cur_word_idx + cur_count > word_len: return False\n",
    "                cur_word_idx += cur_count\n",
    "            else:\n",
    "                if word[cur_word_idx] != abbr[cur_abbr_idx]:\n",
    "                    return False\n",
    "                else:\n",
    "                    cur_abbr_idx += 1\n",
    "                    cur_word_idx += 1\n",
    "        return cur_word_idx == word_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        w = 0\n",
    "        a = 0\n",
    "        cur = ''\n",
    "\n",
    "        while a < len(abbr):\n",
    "            if abbr[a].isdigit():\n",
    "                if len(cur) == 0 and abbr[a] == '0':\n",
    "                    return False\n",
    "                cur += abbr[a]\n",
    "                a += 1\n",
    "\n",
    "            else:\n",
    "                if len(cur) > 0:\n",
    "                    w += int(cur) # update any w\n",
    "                    cur  = ''\n",
    "\n",
    "                if w >= len(word):\n",
    "                    return False\n",
    "\n",
    "                if abbr[a] != word[w]:\n",
    "                    return False\n",
    "                \n",
    "                a += 1\n",
    "                w += 1\n",
    "            \n",
    "        if len(cur) > 0:\n",
    "            w += int(cur)\n",
    "\n",
    "        return w == len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        p1 = p2 = 0\n",
    "        n1, n2 = len(word), len(abbr)\n",
    "\n",
    "        while p1 < n1 and p2 < n2:\n",
    "            if abbr[p2].isdigit():\n",
    "                if abbr[p2] == '0':\n",
    "                    return False\n",
    "                num = 0\n",
    "                while p2 < n2 and abbr[p2].isdigit():\n",
    "                    num = num*10 + int(abbr[p2])\n",
    "                    p2 += 1\n",
    "                p1 += num\n",
    "            else:\n",
    "                if word[p1] != abbr[p2]:\n",
    "                    return False\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "        \n",
    "        return p1 == n1 and p2 == n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        while i < len(word) and j < len(abbr):\n",
    "            if abbr[j].islower():\n",
    "                if word[i] != abbr[j]:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else: \n",
    "                skip = 0\n",
    "                if int(abbr[j]) == 0:\n",
    "                    return False\n",
    "                while j < len(abbr) and abbr[j].isdigit():\n",
    "                    skip = skip * 10 + int(abbr[j])\n",
    "                    j += 1\n",
    "                i += skip\n",
    "        if i == len(word) and j == len(abbr):\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        n = len(word)\n",
    "\n",
    "        m = len(abbr)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < n and j < m:\n",
    "            if \"1\" <= abbr[j] <= \"9\":\n",
    "                num = 0\n",
    "                while j < m and \"0\" <= abbr[j] <= \"9\":\n",
    "                    num = num * 10 + int(abbr[j])\n",
    "                    j += 1\n",
    "                i += num\n",
    "            elif word[i] != abbr[j]:\n",
    "                return False\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return i == n and j == m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        n = len(abbr)\n",
    "        digits = '0123456789'\n",
    "        i = 0\n",
    "        s = []\n",
    "        while i < n:\n",
    "            if abbr[i] in digits:\n",
    "                if abbr[i] == '0':\n",
    "                    return False\n",
    "                j = i + 1\n",
    "                while j < n and abbr[j] in digits:\n",
    "                    j += 1\n",
    "                if int(abbr[i:j]) > len(word):\n",
    "                    return False\n",
    "                for k in range(int(abbr[i:j])):\n",
    "                    s.append('-')\n",
    "                i = j\n",
    "            else:\n",
    "                s.append(abbr[i])\n",
    "                i += 1 \n",
    "        print('word=', word)\n",
    "        print('s=', s)\n",
    "        if len(word) != len(s):\n",
    "            return False\n",
    "        for i in range(len(word)):\n",
    "            if not(s[i] == '-' or s[i] == word[i]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        num=0\n",
    "        p=0\n",
    "        n=len(word)\n",
    "        for i in abbr:\n",
    "            if i.isdigit():\n",
    "                # 如果数字存在前导 0 是不合归的，false s010a\n",
    "                # num用于记录数字\n",
    "                if num==0 and i==\"0\":\n",
    "                    return False\n",
    "                num=num*10+int(i)\n",
    "                # 中断后面的步骤，继续循环i\n",
    "                continue\n",
    "            \n",
    "            if num:\n",
    "                # 指针加了 num 长度之后，需要判断指针是否超过 word长度\n",
    "                p+=num\n",
    "                num=0\n",
    "            # 指针超过 word，或者字母不相符\n",
    "            if p>=n or word[p]!=i:\n",
    "                return  False\n",
    "            p+=1\n",
    "        if p+num==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        point, num, lg = 0, 0, len(word)\n",
    "        for i in abbr:\n",
    "            if i.isdigit():\n",
    "                if num == 0 and i == '0':   # 如果当前 num 是0且 i 也是 '0'，那么缩写是无效的，因为缩写中不应该有前导零\n",
    "                    return False\n",
    "                num = num * 10 + int(i) # 我们将 num 更新为 num * 10 + int(i)。这是因为如果 abbr 中的数字有多位，我们需要将前一位数字乘以10（移位）并加上当前位的数字，比如 abbr 是 \"12\"，初始 num 是1，下一个字符是2\n",
    "                continue\n",
    "            if num: # num 表示 word 中跳过的字符数量\n",
    "                point += num    \n",
    "                num = 0 # num 被重置为0，因为我们开始处理非数字的字符。\n",
    "            if point >= lg or word[point] != i:     # 如果 point 已经大于或等于 lg，或者 word 在 point 的位置的字符不等于 abbr 中的当前字符 i，则缩写无效，函数返回 False。\n",
    "                return False\n",
    "            point += 1  # 如果以上条件都不满足，我们将 point 加1，因为我们成功匹配了一个字符，并且继续前进。\n",
    "        return True if point + num == lg else False # 如果 point + num 等于 lg，表示 word 被完全匹配\n",
    "\n",
    "# point 用于跟踪当前在 word 中的位置。\n",
    "# num 用来累加 abbr 中表示数字的字符。\n",
    "# lg 是 word 的长度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        s = []\n",
    "        x = 0\n",
    "        for c in abbr:\n",
    "            if c.isdigit():\n",
    "                if c == '0' and x == 0:\n",
    "                    return False\n",
    "                x = x * 10 + int(c)\n",
    "                if x > len(word):\n",
    "                    return False\n",
    "            else:\n",
    "                if x:\n",
    "                    s.append('.' * x)\n",
    "                    x = 0\n",
    "                s.append(c)\n",
    "        if x:\n",
    "            s.append('.' * x)\n",
    "        t = ''.join(s)\n",
    "        if len(word) != len(t):\n",
    "            return False\n",
    "        for a, b in zip(word, t):\n",
    "            if b == '.':\n",
    "                continue\n",
    "            if a != b:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        if True:\n",
    "            import re\n",
    "            sub_words = re.split(r\"(\\d+)\", abbr)\n",
    "            sub_nums = [i for i in sub_words if i.isdigit() if i.startswith(\"0\")]\n",
    "            if sub_nums: return False\n",
    "\n",
    "            index = 0\n",
    "            for sub_word in sub_words:\n",
    "                if sub_word.isdigit(): \n",
    "                    index += int(sub_word)\n",
    "                else: \n",
    "                    if word[index:index+len(sub_word)]!= sub_word:\n",
    "                        return False\n",
    "                    index += len(sub_word)\n",
    "            return index == len(word)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        elif False:\n",
    "                \n",
    "            import re\n",
    "            sub_words = re.split(r\"(\\d+)\", abbr)\n",
    "            \n",
    "            #condition\n",
    "            for i, sub_word in enumerate(sub_words):\n",
    "                if sub_word.startswith(\"0\"):\n",
    "                    return False\n",
    "                if sub_word.isdigit():\n",
    "                    if int(sub_word)>=100:\n",
    "                        return False\n",
    "                    else:\n",
    "                        sub_words[i] = \"?\"*int(sub_word)\n",
    "            new_word = \"\".join(sub_words)\n",
    "            if len(word)!= len(new_word):\n",
    "                return False\n",
    "\n",
    "            for sub_zip_word in zip(word, new_word):\n",
    "                print(sub_zip_word)\n",
    "                if sub_zip_word[1] ==\"?\":\n",
    "                    continue\n",
    "                else:\n",
    "                    if sub_zip_word[0] == sub_zip_word[1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "            return True  \n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i = 0\n",
    "        n = len(abbr)\n",
    "        t = []\n",
    "        while i < n:\n",
    "            if abbr[i] == '0':\n",
    "                return False\n",
    "            elif abbr[i].isalpha():\n",
    "                t.append(abbr[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                j = i\n",
    "                s = 0\n",
    "                while j < n and abbr[j].isdigit():\n",
    "                    s = s*10 + ord(abbr[j]) - ord('0')\n",
    "                    j += 1\n",
    "                if s > 20:\n",
    "                    return False\n",
    "                t += ['.'] * s\n",
    "                # print(f't = {t}, s= {s}')\n",
    "                i = j\n",
    "        t = \"\".join(t)\n",
    "        # print(f't = {t}')\n",
    "        if len(t) != len(word): return False\n",
    "        for x, y in zip(word, t):\n",
    "            if x != y and y != '.':\n",
    "                return False\n",
    "        return True \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        m, n = len(word), len(abbr)\n",
    "        num = \"\"\n",
    "        i, j = 0, 0 # this line\n",
    "        while i < m and j < n:\n",
    "            if word[i] == \" \":\n",
    "                i += 1\n",
    "            elif word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                if not abbr[j].isnumeric(): # this logic is important\n",
    "                    return False\n",
    "                if abbr[j] == \"0\":\n",
    "                    return False\n",
    "                while j < n and abbr[j].isnumeric(): # j <n important\n",
    "                    num += abbr[j]\n",
    "                    j += 1\n",
    "                count = int(num)\n",
    "                num = \"\"\n",
    "                if i + count <= m: # why this is wrong\n",
    "                    i += count\n",
    "                    count = 0\n",
    "                else:\n",
    "                    return False\n",
    "                # i += count\n",
    "     \n",
    "        return i == m and j == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        n, m = len(word), len(abbr)\n",
    "        i, j = 0, 0\n",
    "        while i < n and j < m:\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] == \"0\":\n",
    "                    return False\n",
    "                s = j\n",
    "                while j+1 < m and abbr[j+1].isdigit():\n",
    "                    j += 1\n",
    "                l = int(abbr[s:j+1])\n",
    "                if i + l > n:\n",
    "                    return False\n",
    "                i += l\n",
    "                j += 1\n",
    "            else:\n",
    "                if word[i] == abbr[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "        return True if i==n and j==m else False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        n = len(word)\n",
    "        # 记录数字\n",
    "        num = 0\n",
    "        p = 0\n",
    "        \n",
    "        for ch in abbr:\n",
    "            if ch.isdigit():\n",
    "                if num==0 and ch == '0':\n",
    "                    return False\n",
    "                num = num*10+int(ch)\n",
    "            else:\n",
    "                p += num\n",
    "                if p>=n or ch!=word[p]:\n",
    "                    return False\n",
    "                num = 0\n",
    "                p += 1\n",
    "        return p+num==n\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        abbr_equal_len = 0\n",
    "        num = 0\n",
    "        for c in abbr:\n",
    "            if c.isdigit():\n",
    "                if num == 0 and c == '0':\n",
    "                    return False\n",
    "                num = num * 10 + int(c)\n",
    "            else:\n",
    "                abbr_equal_len += num\n",
    "                num = 0\n",
    "                # increment\n",
    "                abbr_equal_len += 1\n",
    "                if abbr_equal_len > len(word) or c != word[abbr_equal_len - 1]:\n",
    "                    return False\n",
    "        abbr_equal_len += num\n",
    "        return abbr_equal_len == len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "\n",
    "        length = 0\n",
    "        num = 0\n",
    "        for c in abbr:\n",
    "            if c.isdigit():\n",
    "                if c == '0' and num == 0: return False\n",
    "                num = num * 10 + int(c)\n",
    "            else:\n",
    "                length += num\n",
    "                num = 0\n",
    "                # print(length, word[length])\n",
    "                if length >= len(word) or word[length]!= c:\n",
    "                    return False \n",
    "                \n",
    "                length += 1\n",
    "\n",
    "        \n",
    "        length += num\n",
    "        return length == len(word)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        if True:\n",
    "            import re\n",
    "            sub_words = re.split(r\"(\\d+)\", abbr)\n",
    "            sub_nums = [i for i in sub_words if i.isdigit() if i.startswith(\"0\")]\n",
    "            if sub_nums: return False\n",
    "\n",
    "            index = 0\n",
    "            for sub_word in sub_words:\n",
    "                if sub_word.isdigit():  index += int(sub_word)\n",
    "                else: \n",
    "                    if word[index:index+len(sub_word)]!= sub_word: return False\n",
    "                    index += len(sub_word)\n",
    "            return index == len(word)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        elif False:\n",
    "                \n",
    "            import re\n",
    "            sub_words = re.split(r\"(\\d+)\", abbr)\n",
    "            \n",
    "            #condition\n",
    "            for i, sub_word in enumerate(sub_words):\n",
    "                if sub_word.startswith(\"0\"):\n",
    "                    return False\n",
    "                if sub_word.isdigit():\n",
    "                    if int(sub_word)>=100:\n",
    "                        return False\n",
    "                    else:\n",
    "                        sub_words[i] = \"?\"*int(sub_word)\n",
    "            new_word = \"\".join(sub_words)\n",
    "            if len(word)!= len(new_word):\n",
    "                return False\n",
    "\n",
    "            for sub_zip_word in zip(word, new_word):\n",
    "                print(sub_zip_word)\n",
    "                if sub_zip_word[1] ==\"?\":\n",
    "                    continue\n",
    "                else:\n",
    "                    if sub_zip_word[0] == sub_zip_word[1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "            return True  \n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i , j = 0, 0\n",
    "        m, n = len(word), len(abbr)\n",
    "        \n",
    "        while i < m and j <n:\n",
    "            if word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif abbr[j] == \"0\":\n",
    "                return False\n",
    "            elif abbr[j].isdigit():\n",
    "                k = j\n",
    "                while k < n and abbr[k].isdigit():\n",
    "                    k += 1\n",
    "                i += int(abbr[j:k])\n",
    "                j = k\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return i == m and j == n\n",
    "                \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        abbr_pos = 0 \n",
    "        num = 0 \n",
    "        for c in abbr:\n",
    "            if c.isdigit() != 0: # 是数字\n",
    "                if num == 0 and c == '0':\n",
    "                    return False\n",
    "                num = num * 10 + int(c)\n",
    "            else:\n",
    "                abbr_pos += num \n",
    "                num = 0\n",
    "                abbr_pos += 1\n",
    "                if abbr_pos > len(word) or c != word[abbr_pos-1]:\n",
    "                    return False\n",
    "        abbr_pos += num\n",
    "        return abbr_pos == len(word) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        num = 0 #指针指到的abbr的数字\n",
    "        abbr_len = 0 #指针指到的abbr的数字\n",
    "        for i in abbr:\n",
    "            if i.isdigit() != 0: #如果当前是数字\n",
    "                if i == '0' and num == 0:\n",
    "                    return False\n",
    "                num = num * 10+ int(i) \n",
    "            else:\n",
    "                abbr_len += num \n",
    "                num = 0\n",
    "                abbr_len += 1\n",
    "                if abbr_len > len(word) or i != word[abbr_len - 1]:\n",
    "                    return False\n",
    "        abbr_len += num\n",
    "        return abbr_len == len(word)\n",
    "                \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i, n = 0, len(word)\n",
    "        for x in re.findall(r'([a-z]|\\d+)', abbr):\n",
    "            if x.isalpha():\n",
    "                if i >= n or word[i] != x:\n",
    "                    return False\n",
    "                i += 1\n",
    "            else:\n",
    "                if x[0] == '0':\n",
    "                    return False\n",
    "                i += int(x)\n",
    "                if i > n:\n",
    "                    return False\n",
    "        return i == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(word) and j < len(abbr):\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] == \"0\":\n",
    "                    return False\n",
    "                start = j\n",
    "                while start < len(abbr) and abbr[start].isdigit():\n",
    "                    start += 1\n",
    "                \n",
    "                i += int(abbr[j:start])\n",
    "                j = start\n",
    "                continue\n",
    "            \n",
    "            if word[i] != abbr[j]:\n",
    "                return False\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        return i == len(word) and j == len(abbr)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        p, q = 0, 0\n",
    "        l = len(word)\n",
    "        n = 0\n",
    "        for idx, c in enumerate(abbr):\n",
    "            if 'a'<=c<='z':\n",
    "                p += n\n",
    "                n = 0\n",
    "                if p>=l or (word[p] != c):\n",
    "                    return False\n",
    "                else:\n",
    "                    p+=1\n",
    "            elif '0'<=c<='9':\n",
    "                if c=='0' and n==0:\n",
    "                    return False\n",
    "                n = n*10 + int(c)\n",
    "        if len(word) == p+n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        word = list(word)\n",
    "        tmp = []\n",
    "        idx = 0\n",
    "        # 1. 把缩写展开，任何被缩写的子字符串用'*'代替\n",
    "        while idx < len(abbr):\n",
    "            if abbr[idx].isdigit():\n",
    "                # 缩写不能存在前导零\n",
    "                if abbr[idx] == '0': return False\n",
    "                num = ''\n",
    "                while idx < len(abbr) and abbr[idx].isdigit():\n",
    "                    num += abbr[idx]\n",
    "                    idx += 1\n",
    "                if int(num) > len(word): return False\n",
    "                tmp += list('*'*int(num))\n",
    "            else:\n",
    "                tmp.append(abbr[idx])\n",
    "                idx += 1\n",
    "\n",
    "        if len(word) != len(tmp): return False\n",
    "        # 2. 将展开后的缩写与word对比，'*'可以对应任何一个单词\n",
    "        for i in range(len(word)):\n",
    "            if tmp[i] != '*' and tmp[i] != word[i]: return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        m, n = len(word), len(abbr)\n",
    "        num = \"\"\n",
    "        i, j = 0, 0 # this line\n",
    "        while i < m and j < n:\n",
    "            if word[i] == \" \":\n",
    "                i += 1\n",
    "            elif word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                if not abbr[j].isnumeric(): # this logic is important\n",
    "                    return False\n",
    "                if abbr[j] == \"0\":\n",
    "                    return False\n",
    "                while j < n and abbr[j].isnumeric(): # j <n important\n",
    "                    num += abbr[j]\n",
    "                    j += 1\n",
    "                count = int(num)\n",
    "                num = \"\"\n",
    "                # if i + count <= m: # < is wrong, should be <=\n",
    "                #     i += count\n",
    "                #     count = 0\n",
    "                # else:\n",
    "                #     return False\n",
    "                i += count # the above is optional\n",
    "     \n",
    "        return i == m and j == n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        if True:\n",
    "            import re\n",
    "            sub_words = re.split(r\"(\\d+)\", abbr)\n",
    "            sub_nums = [i for i in sub_words if i.isdigit() and i.startswith(\"0\")]\n",
    "            if sub_nums: return False\n",
    "\n",
    "            index = 0\n",
    "            for sub_word in sub_words:\n",
    "                if not sub_word.isdigit() and word[index:index+len(sub_word)]!= sub_word: return False\n",
    "                index += int(sub_word) if sub_word.isdigit() else len(sub_word)\n",
    "            return index == len(word)\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        elif False:\n",
    "                \n",
    "            import re\n",
    "            sub_words = re.split(r\"(\\d+)\", abbr)\n",
    "            \n",
    "            #condition\n",
    "            for i, sub_word in enumerate(sub_words):\n",
    "                if sub_word.startswith(\"0\"):\n",
    "                    return False\n",
    "                if sub_word.isdigit():\n",
    "                    if int(sub_word)>=100:\n",
    "                        return False\n",
    "                    else:\n",
    "                        sub_words[i] = \"?\"*int(sub_word)\n",
    "            new_word = \"\".join(sub_words)\n",
    "            if len(word)!= len(new_word):\n",
    "                return False\n",
    "\n",
    "            for sub_zip_word in zip(word, new_word):\n",
    "                print(sub_zip_word)\n",
    "                if sub_zip_word[1] ==\"?\":\n",
    "                    continue\n",
    "                else:\n",
    "                    if sub_zip_word[0] == sub_zip_word[1]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "            return True  \n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Boring implementation detail question, review and recite.\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        if not word and not abbr: return True\n",
    "        if not word or not abbr: return False\n",
    "        if abbr[0].isdigit():\n",
    "            if abbr[0] == '0': return False\n",
    "            cur_idx, cur_count = 0, 0\n",
    "            while cur_idx < len(abbr) and abbr[cur_idx].isdigit():\n",
    "                cur_count = cur_count * 10 + int(abbr[cur_idx])\n",
    "                cur_idx += 1\n",
    "            if cur_count > len(word): return False\n",
    "            return self.validWordAbbreviation(word[cur_count:], abbr[cur_idx:])\n",
    "        if abbr[0] != word[0]: return False\n",
    "        return self.validWordAbbreviation(word[1:], abbr[1:])\n",
    "    \n",
    "    \n",
    "    def validWordAbbreviation2(self, word: str, abbr: str) -> bool:\n",
    "        word_len, abbr_len = len(word), len(abbr)\n",
    "        cur_word_idx, cur_abbr_idx = 0, 0\n",
    "        while cur_abbr_idx < abbr_len:\n",
    "            if cur_word_idx >= word_len: return False\n",
    "            cur_count = 0\n",
    "            while cur_abbr_idx < abbr_len and abbr[cur_abbr_idx].isdigit(): # 1RE: index out of range\n",
    "                if cur_count == 0 and abbr[cur_abbr_idx] == '0': return False # 2WA: leading zero return false, need confirm with interviewer\n",
    "                cur_count = cur_count * 10 + int(abbr[cur_abbr_idx])\n",
    "                cur_abbr_idx += 1\n",
    "            if cur_count != 0:\n",
    "                if cur_word_idx + cur_count > word_len: return False\n",
    "                cur_word_idx += cur_count\n",
    "            else:\n",
    "                if word[cur_word_idx] != abbr[cur_abbr_idx]:\n",
    "                    return False\n",
    "                else:\n",
    "                    cur_abbr_idx += 1\n",
    "                    cur_word_idx += 1\n",
    "        return cur_word_idx == word_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        w = 0\n",
    "        a = 0\n",
    "        cur = 0\n",
    "\n",
    "        while a < len(abbr) and w < len(word):\n",
    "            if abbr[a].isdigit():\n",
    "                if cur == 0 and abbr[a] == '0':\n",
    "                    return False\n",
    "                cur = cur * 10 + int(abbr[a])\n",
    "                a += 1\n",
    "\n",
    "            else:               \n",
    "                w += int(cur) # update any w\n",
    "                cur = 0\n",
    "\n",
    "                if w >= len(word):\n",
    "                    return False\n",
    "\n",
    "                if abbr[a] != word[w]:\n",
    "                    return False\n",
    "                \n",
    "                a += 1\n",
    "                w += 1\n",
    "            \n",
    "        \n",
    "        w += int(cur)\n",
    "\n",
    "        return w == len(word) and a == len(abbr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        m, n = len(word), len(abbr)\n",
    "        i, j = 0, 0\n",
    " \n",
    "        while i < m and j < n:\n",
    "            num = 0\n",
    "            if word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif word[i] != abbr[j]:\n",
    "                if abbr[j].isalpha():\n",
    "                    return False\n",
    "                if abbr[j] == \"0\": # this logic\n",
    "                    return False \n",
    "                while j < n and abbr[j].isnumeric():\n",
    "                    num = num * 10 + int(abbr[j])\n",
    "                    j += 1\n",
    "            # print(word[i: i+ num])\n",
    "            if num > 0:\n",
    "                if i + num > m: # I + num is the next pos so >= is wrong\n",
    "                    return False\n",
    "                else:\n",
    "                    i += num\n",
    "        return i == m and j == n # this line!!!\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        m, n = len(word), len(abbr)\n",
    "\n",
    "        while i < m and j < n:\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] == '0': return False\n",
    "                abb_len = 0\n",
    "                while j < n and abbr[j].isdigit():\n",
    "                    abb_len = abb_len * 10 + int(abbr[j])\n",
    "                    j += 1\n",
    "                # move forward with equal len of word\n",
    "                i += abb_len\n",
    "\n",
    "            # abbr[j] is letter\n",
    "            else:\n",
    "                if word[i] != abbr[j]: \n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "        return i == m and j == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        acnt = 0\n",
    "        while i < len(word) and j < len(abbr):\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] == \"0\":\n",
    "                    return False\n",
    "                else:\n",
    "                    while j < len(abbr) and abbr[j].isdigit():\n",
    "                        acnt = acnt * 10 + int(abbr[j])\n",
    "                        j += 1\n",
    "            i += acnt\n",
    "            #print(i, j)\n",
    "            if i < len(word) and j < len(abbr) and word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                acnt = 0\n",
    "            elif (i == len(word) and j == len(abbr)):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "        return True if (i == len(word) and j == len(abbr)) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        while p1 < len(word) and p2 < len(abbr):\n",
    "            if word[p1] == abbr[p2]:\n",
    "                p1 = p1 + 1\n",
    "                p2 = p2 + 1\n",
    "            else:\n",
    "                if not abbr[p2].isdigit():\n",
    "                    return False\n",
    "                if int(abbr[p2]) == 0:\n",
    "                    return False\n",
    "                length = ''\n",
    "                while p2 < len(abbr) and abbr[p2].isdigit():\n",
    "                    length = length + abbr[p2]\n",
    "                    p2 = p2 + 1\n",
    "                length = int(length)\n",
    "                if length+p1 > len(word):\n",
    "                    return False\n",
    "                else:\n",
    "                    p1 = p1 + length\n",
    "        if p2 != len(abbr) or p1 != len(word):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        num = 0  # number between alphas in abbr\n",
    "        abbrLen = 0 # corresponding index in the word\n",
    "        for i in range(len(abbr)):\n",
    "            if abbr[i].isalpha():\n",
    "                abbrLen += num+1\n",
    "                num = 0\n",
    "                if abbrLen > len(word) or word[abbrLen-1] != abbr[i]:\n",
    "                    return False\n",
    "            else:\n",
    "                if num==0 and abbr[i]=='0':\n",
    "                    return False\n",
    "                num = num*10 + int(abbr[i])\n",
    "        \n",
    "        return abbrLen+num == len(word)\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(word) and j < len(abbr):\n",
    "            if word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                continue\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] =='0': return False\n",
    "                cnt = 0\n",
    "                k = j \n",
    "                while k < len(abbr) and abbr[k].isdigit():\n",
    "                    cnt = cnt * 10 + int(abbr[k])\n",
    "                    k += 1\n",
    "                i += cnt \n",
    "                j = k\n",
    "            else:\n",
    "                break \n",
    "        return i == len(word) and j == len(abbr)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        c1, c2 = 0, 0\n",
    "        num = 0\n",
    "\n",
    "        while c1 < len(abbr):\n",
    "            if abbr[c1].isalpha():\n",
    "                # check if chars are matching\n",
    "                c2 += num\n",
    "                if c2 >= len(word):\n",
    "                    return False\n",
    "                if abbr[c1] != word[c2]:\n",
    "                    return False\n",
    "                num = 0\n",
    "                c2 += 1\n",
    "            else:\n",
    "                if abbr[c1] == '0' and num == 0:\n",
    "                    return False\n",
    "                # it's a number\n",
    "                num = int(abbr[c1]) + 10 * num\n",
    "            c1 += 1\n",
    "        c2 += num\n",
    "        return c2 == len(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        m, n = len(word), len(abbr)\n",
    "        i = j = x = 0\n",
    "        while i < m and j < n:\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] == '0' and x == 0:\n",
    "                    return False\n",
    "                x = x * 10 + int(abbr[j])\n",
    "            else:\n",
    "                i += x\n",
    "                x = 0\n",
    "                if i >= m or word[i] != abbr[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return i + x == m and j == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i = 0\n",
    "        tmp = []\n",
    "        while i < len(abbr):\n",
    "            if abbr[i] == '0' and i + 1 < len(abbr) and abbr[i + 1].isdigit():\n",
    "                return False\n",
    "            if abbr[i] == '0' and i + 1 < len(abbr) and abbr[i + 1].isalpha():\n",
    "                return False\n",
    "\n",
    "            if abbr[i].isalpha():\n",
    "                tmp.append(abbr[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                k = i + 1\n",
    "\n",
    "                while k < len(abbr) and abbr[k].isdigit():\n",
    "                    k += 1\n",
    "\n",
    "                n_replacement = int(abbr[i:k])\n",
    "\n",
    "                if n_replacement > len(word):\n",
    "                    return False\n",
    "\n",
    "                tmp.extend(['*'] * n_replacement)\n",
    "\n",
    "                i = k\n",
    "\n",
    "        if len(word) != len(tmp):\n",
    "            return False\n",
    "\n",
    "        for i in range(len(word)):\n",
    "            if tmp[i] != \"*\" and word[i] != tmp[i]:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i = 0 \n",
    "        digit = 0\n",
    "        for j in range(len(abbr)):\n",
    "            if abbr[j].isdigit():\n",
    "                if digit == 0 and int(abbr[j]) == 0:\n",
    "                    return False\n",
    "                digit = digit * 10 + int(abbr[j])\n",
    "            else:\n",
    "                i = i + digit\n",
    "                digit = 0\n",
    "                if i >= len(word) or word[i] != abbr[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "        if digit > 0:\n",
    "            i += digit \n",
    "        # print(i, len(word))\n",
    "        return i == len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        n1, n2 = len(word), len(abbr)\n",
    "        p1 = p2 = 0\n",
    "\n",
    "        while p1 < n1 and p2 < n2:\n",
    "            if abbr[p2] == '0':\n",
    "                return False\n",
    "            if abbr[p2].isdigit():\n",
    "                num = 0\n",
    "                while p2 < n2 and abbr[p2].isdigit():\n",
    "                    num = num*10 + int(abbr[p2])\n",
    "                    p2 += 1\n",
    "                p1 += num \n",
    "            else:\n",
    "                if word[p1] != abbr[p2]:\n",
    "                    return False\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "        \n",
    "        return p1 == n1 and p2 == n2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i=0\n",
    "        j=0\n",
    "        \n",
    "\n",
    "        while i<len(word) and j<len(abbr):\n",
    "            if word[i]==abbr[j]:\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif abbr[j].isdigit():\n",
    "                num=0\n",
    "                while j<len(abbr) and abbr[j].isdigit():\n",
    "                    if num==0 and int(abbr[j])==0:\n",
    "                        return False\n",
    "                    num=num*10+int(abbr[j])\n",
    "                    j+=1\n",
    "                i+=num\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return i==len(word) and j==len(abbr)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i1, i2 = 0, 0\n",
    "        n1, n2 = len(word), len(abbr)\n",
    "        pre_num = False\n",
    "        while i1 < n1 and i2 < n2:\n",
    "            if word[i1] == abbr[i2]:\n",
    "                i1 += 1\n",
    "                i2 += 1\n",
    "                pre_num = False\n",
    "            else:\n",
    "                if 'a' <= abbr[i2] <= 'z' or abbr[i2] == '0' or pre_num:\n",
    "                    return False\n",
    "                cur = 0\n",
    "                while i2 < n2 and '0' <= abbr[i2] <= '9':\n",
    "                    cur *= 10\n",
    "                    cur += int(abbr[i2])\n",
    "                    i2 += 1\n",
    "                i1 += cur\n",
    "                pre_num = True\n",
    "        return i1 == n1 and i2 == n2\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        nw, na = len(word), len(abbr)\n",
    "        pw = pa = 0\n",
    "\n",
    "        while pw < nw and pa < na:\n",
    "            if abbr[pa].isdigit():\n",
    "                if abbr[pa] == '0':\n",
    "                    return False\n",
    "                num = 0\n",
    "                while pa < na and abbr[pa].isdigit():\n",
    "                    num = num*10 + int(abbr[pa])\n",
    "                    pa += 1\n",
    "                pw += num\n",
    "            else:\n",
    "                if word[pw] != abbr[pa]:\n",
    "                    return False\n",
    "                pw += 1\n",
    "                pa += 1\n",
    "        \n",
    "        return pw == nw and pa == na\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "#     对于数字，尤其多位数字我们需要维护一个临时的num用于记录。\n",
    "# `当出现多位数字时，使用num = num * 10 + int(i)的方式追加。\n",
    "# 每次在指针追加num后，都需要判断指针是否以超过word总长\n",
    "# 对于`数字出现在最后的问题，需要在末尾添加point+num的操作后再进行判断\n",
    "\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        num=0\n",
    "        p=0\n",
    "        n=len(word)\n",
    "        for i in abbr:\n",
    "            if i.isdigit():\n",
    "                # 如果数字存在前导 0 是不合归的，false s010a\n",
    "                # num用于记录数字\n",
    "                if num==0 and i==\"0\":\n",
    "                    return False\n",
    "                num=num*10+int(i)\n",
    "                # 中断后面的步骤，继续循环i\n",
    "                continue\n",
    "            \n",
    "            if num:\n",
    "                # 指针加了 num 长度之后，需要判断指针是否超过 word长度\n",
    "                p+=num\n",
    "                num=0\n",
    "            # 指针超过 word，或者字母不相符\n",
    "            if p>=n or word[p]!=i:\n",
    "                return  False\n",
    "            p+=1\n",
    "        if p+num==n:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, b: str, a: str) -> bool:\n",
    "        #TWO POINTERS\n",
    "        i,j=0,0\n",
    "        x=0\n",
    "        while i < len(a):\n",
    "            ch = a[i]\n",
    "            if ch.isdigit():\n",
    "                if ch=='0': \n",
    "                    return False\n",
    "                while i<len(a) and a[i].isdigit():\n",
    "                    x=10*x+int(a[i])\n",
    "                    i+=1\n",
    "            else:\n",
    "                j+=x+1\n",
    "                x=0\n",
    "                if(j-1>=len(b) or b[j-1]!=a[i]):\n",
    "                    return False\n",
    "                i+=1\n",
    "        return j+x == len(b)\n",
    "            \n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        j = 0\n",
    "        num = 0\n",
    "        for i in range(len(abbr)):\n",
    "            if \"a\"<=abbr[i]<=\"z\":\n",
    "                j += num\n",
    "                num = 0\n",
    "                if j < len(word) and abbr[i] == word[j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif abbr[i].isdigit():\n",
    "                if num == 0 and abbr[i] == \"0\":\n",
    "                    return False\n",
    "                num = 10 * num + int(abbr[i])\n",
    "        return j+num == len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i, j = 0, 0\n",
    "        m, n = len(word), len(abbr)\n",
    "        while i < m and j < n:\n",
    "            if abbr[j].isdigit():\n",
    "                if abbr[j] == '0':\n",
    "                    return False\n",
    "                num = 0\n",
    "                while j < n and abbr[j].isdigit():\n",
    "                    num = num * 10 + int(abbr[j])\n",
    "                    j += 1\n",
    "                i += num\n",
    "            else:\n",
    "                if word[i] != abbr[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return i == m and j == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        j = 0\n",
    "        num = 0\n",
    "        for i in range(len(abbr)):\n",
    "            if \"a\"<=abbr[i]<=\"z\":\n",
    "                j += num\n",
    "                num = 0\n",
    "                if j < len(word) and abbr[i] == word[j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            elif abbr[i].isdigit():\n",
    "                if num == 0 and abbr[i] == \"0\":\n",
    "                    return False\n",
    "                num = 10 * num + int(abbr[i])\n",
    "        if num > 0:\n",
    "            j += num\n",
    "        if j != len(word):\n",
    "            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        l,r,cur=0,0,0\n",
    "        for r in range(len(abbr)):\n",
    "            if abbr[r].isalpha():\n",
    "                for _ in range(cur):\n",
    "                    if l==len(word):\n",
    "                        return False\n",
    "                    l+=1\n",
    "                if l==len(word) or abbr[r]!=word[l]:\n",
    "                    return False\n",
    "                else:\n",
    "                    l+=1\n",
    "                cur=0\n",
    "            else:\n",
    "                if abbr[r]==\"0\" and cur==0:\n",
    "                    return False\n",
    "                else:\n",
    "                    cur=cur*10+int(abbr[r])\n",
    "        for _ in range(cur):\n",
    "            if l>len(word):\n",
    "                return False\n",
    "            l+=1\n",
    "        return l==len(word)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Boring implementation detail question, review and recite.\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation2(self, word: str, abbr: str) -> bool:\n",
    "        if not word and not abbr: return True\n",
    "        if not word or not abbr: return False\n",
    "        if abbr[0].isdigit():\n",
    "            if abbr[0] == '0': return False\n",
    "            cur_idx, cur_count = 0, 0\n",
    "            while cur_idx < len(abbr) and abbr[cur_idx].isdigit():\n",
    "                cur_count = cur_count * 10 + int(abbr[cur_idx])\n",
    "                cur_idx += 1\n",
    "            if cur_count > len(word): return False\n",
    "            return self.validWordAbbreviation(word[cur_count:], abbr[cur_idx:])\n",
    "        if abbr[0] != word[0]: return False\n",
    "        return self.validWordAbbreviation(word[1:], abbr[1:])\n",
    "    \n",
    "    \n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        word_len, abbr_len = len(word), len(abbr)\n",
    "        cur_word_idx, cur_abbr_idx = 0, 0\n",
    "        while cur_abbr_idx < abbr_len and cur_word_idx < word_len:\n",
    "            if abbr[cur_abbr_idx].isdigit():\n",
    "                if abbr[cur_abbr_idx] == '0': return False\n",
    "                cur_count = 0\n",
    "                while cur_abbr_idx < abbr_len and abbr[cur_abbr_idx].isdigit():\n",
    "                    cur_count = cur_count * 10 + int(abbr[cur_abbr_idx])\n",
    "                    cur_abbr_idx += 1\n",
    "                cur_word_idx += cur_count\n",
    "            else:\n",
    "                if abbr[cur_abbr_idx] != word[cur_word_idx]:\n",
    "                    return False\n",
    "                cur_abbr_idx += 1\n",
    "                cur_word_idx += 1\n",
    "        return cur_word_idx == word_len and cur_abbr_idx == abbr_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        i = j = 0\n",
    "        while i < len(word) and j < len(abbr):\n",
    "            if word[i] == abbr[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                continue\n",
    "            # 不等的时候或abbr中为0开头返回False\n",
    "            if abbr[j] <= '0' or abbr[j] > '9':\n",
    "                return False\n",
    "            num = 0\n",
    "            while j < len(abbr) and '0' <= abbr[j] <= '9':\n",
    "                num = 10 * num + int(abbr[j])\n",
    "                j += 1\n",
    "            i += num\n",
    "        return i == len(word) and j == len(abbr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        \n",
    "        cur_digit = 0\n",
    "        abbr_len = 0\n",
    "\n",
    "        for val in abbr:\n",
    "            if  \"0\" <= val <= \"9\":\n",
    "                if val == '0' and cur_digit == 0:\n",
    "                    return False\n",
    "                cur_digit = cur_digit*10 + ord(val) - ord(\"0\")\n",
    "            else:\n",
    "                abbr_len += cur_digit\n",
    "                cur_digit = 0\n",
    "                if len(word) <= abbr_len:\n",
    "                    return False\n",
    "                if word[abbr_len] != val:\n",
    "                    return False\n",
    "                abbr_len += 1\n",
    "\n",
    "        print(abbr_len, cur_digit, len(word))\n",
    "        if len(word) != abbr_len+cur_digit:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validWordAbbreviation(self, word: str, abbr: str) -> bool:\n",
    "        S, val = '', 0\n",
    "        m, n = len(word), len(abbr)\n",
    "        for i in range(n):\n",
    "            if i == 0 and abbr[i] == '0': return False\n",
    "            if abbr[i-1].isalpha() and abbr[i] == '0': return False\n",
    "        for s in abbr:\n",
    "            if s.isdigit():\n",
    "                val = 10 * val + int(s)\n",
    "                if val > m: return False\n",
    "            else:\n",
    "                S += '.' * val\n",
    "                S += s\n",
    "                val = 0\n",
    "        if val: S += '.' * val\n",
    "        if len(S) != len(word): return False\n",
    "        for s, t in zip(S, word):\n",
    "            if s == '.':\n",
    "                continue\n",
    "            else:\n",
    "                if s != t:\n",
    "                    return False\n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
